package com.atguigu.algorithm.search;

/**
 * 插值法查找
 * 思路同二分查找法，仅mid的计算公式不同
 * mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low])
 * @author xr-8
 * @date 2022-09-12
 * @time 23:26
 */
public class InsertValueSearch {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(search(arr, 0, arr.length - 1, 10));
    }

    public static int search(int[] arr, int min, int max, int num) {
        if (min > max || arr[min] > num || arr[max] < num) {
            return -1;
        }
        // 求出mid, 自适应
        int mid = min + (max - min) * (num - arr[min]) / (arr[max] - arr[min]);
        if (arr[mid] > num) {
            return search(arr, min, mid - 1, num);
        } else if (arr[mid] < num) {
            return search(arr, mid + 1, max, num);
        } else {
            return mid;
        }
    }
}
